翻訳と辞書 Words near each other ・ Gap junction ・ Gap junction protein ・ GAP line ・ Gap loss ・ Gap Mangione ・ Gap Mills, West Virginia ・ Gap Mountain ・ Gap Mountains ・ Gap Nunatak ・ Gap of Dunloe ・ Gap penalty ・ Gap Powell ・ Gap Puche Cabin ・ Gap Queens Park F.C. ・ Gap reduction ・ Gap theorem ・ Gap theorem (disambiguation) ・ Gap View Farm ・ GAP waiver ・ Gap wedge ・ Gap Yah ・ Gap year ・ Gap, Hautes-Alpes ・ Gap, New South Wales ・ Gap, North Carolina ・ Gap, Pennsylvania ・ Gap-43 protein ・ Gap-dong ・ Gapa ・ Gapa Hele Bi Sata Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Gap theorem ： ウィキペディア英語版 Gap theorem :''See also Gap theorem (disambiguation) for other gap theorems in mathematics.'' In computational complexity theory the Gap Theorem, also known as the Borodin-Trakhtenbrot Gap Theorem, is a major theorem about the complexity of computable functions. It essentially states that there are arbitrarily large computable gaps in the hierarchy of complexity classes. For any computable function that represents an increase in computational resources, one can find a resource bound such that the set of functions computable within the expanded resource bound is the same as the set computable within the original bound. The theorem was proved independently by Boris Trakhtenbrotand Allan Borodin. == Gap theorem == The general form of the theorem is as follows. :Suppose $\backslash Phi$ is an abstract (Blum) complexity measure. For any total computable function ''g'' for which $g(x)\; \backslash geq\; x$ for every $\backslash ,x$, there is a total computable function ''t'' such that with respect to $\backslash Phi$, the complexity classes with boundary functions $t$ and $g\; \backslash circ\; t$ are identical. The theorem can be proved by using the Blum axioms without any reference to a concrete computational model, so it applies to time, space, or any other reasonable complexity measure. For the special case of time complexity, this can be stated more simply as: :for any total computable function $g\; \backslash ,\; :\; \backslash ,\; \backslash omega\; \backslash ,\backslash to\backslash ,\; \backslash omega$ such that $g(x)\; \backslash geq\; x$ for all $\backslash ,x$, there exists a time bound $T(n)$ such that $DTIME(g(T(n)))\; =\; DTIME(T(n))$. Because the bound ''T(n)'' may be very large (and often will be nonconstructible) the Gap Theorem does not imply anything interesting for complexity classes such as P or NP,〔.〕 and it does not contradict the time hierarchy theorem or space hierarchy theorem.〔.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Gap theorem」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.